如果没有不能走到的点,这道题就非常简单了。我们只需向下走步,向右走步,就可到达右下角。在这步中,我们选向下走,那么答案为。
但是,棋盘中有些点是不能走的,我们考虑用容斥原理去除多余方案,即
其中,经过个不能走的点的路径,但是,此题,容斥原理直接炸掉。
但上面的思路给了我们启示,设表示从走到第个不能走的点,且不经过其它不能走的点的方案数。那么有:

我们可以看出,转移时与下标先后顺序有关,我们先对下标排序,再进行计算。
我们将终点也看成一个不能走到的点,答案就为
附上代码:
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define Mod 1000000007
const int MAXN = 2000 , MAXDEX = 100000;
int h , w , n , f[ MAXN + 5 ];
int Fac[ 2 * MAXDEX + 5 ] , Inv[ 2 * MAXDEX + 5 ];
struct node{
int x , y;
bool operator < ( const node &Other ) {
if( x < Other.x )
return 1;
if( x == Other.x && y < Other.y )
return 1;
return 0;
}
}a[ MAXN + 5 ];
int Quick_pow( int x , int po ) {
int Ans = 1;
while( po ) {
if( po % 2 )
Ans = 1ll * Ans * x % Mod;
x = 1ll * x * x % Mod;
po /= 2;
}
return Ans;
}
void Init( ) {
int M = 2 * max( h , w );
Fac[ 0 ] = 1;
for( int i = 1 ; i <= M ; i ++ )
Fac[ i ] = 1ll * Fac[ i - 1 ] * i % Mod;
Inv[ M ] = Quick_pow( Fac[ M ] , Mod - 2 ); //费马小定理算出阶乘最后一项逆元
for( int i = M - 1 ; i >= 0 ; i -- )
Inv[ i ] = 1ll * Inv[ i + 1 ] * ( i + 1 ) % Mod;
/*for( int i = 1 ; i <= M ; i ++ )
printf("%d %d\n",Fac[ i ],Inv[ i ]);*/
}
int Combination( int n , int m ) { //根据组合数定义
if( n < m ) return 0;
return 1ll * Fac[ n ] * Inv[ n - m ] % Mod * Inv[ m ] % Mod;
}
int main( ) {
scanf("%d %d %d",& h , &w , &n );
for( int i = 1 ; i <= n ; i ++ )
scanf("%d %d",&a[ i ].x,&a[ i ].y);
n ++;
a[ n ].x = h , a[ n ].y = w;
sort( a + 1 , a + n + 1 );
Init( );
for( int i = 1 ; i <= n ; i ++ ) {
f[ i ] = Combination( a[ i ].x + a[ i ].y - 2 , a[ i ].x - 1 );
for( int j = 1 ; j <= i - 1 ; j ++ )
f[ i ] = ( ( 1ll * f[ i ] - 1ll * f[ j ] * Combination( a[ i ].x + a[ i ].y - a[ j ].x - a[ j ].y , a[ i ].x - a[ j ].x ) % Mod ) % Mod + Mod ) % Mod;
}
printf("%d\n",f[ n ]);
return 0;
}